package com.leetcode;

public class lc1005 {

    public int largestSumAfterKNegations(int[] A, int K) {
        int sum = 0;
        int[] dp = new int[101];
        int negative = 0;
        int min = 101;
        for(int a : A){
            min = Math.min(min,Math.abs(a));
            sum += a;
            if(a < 0){
                a = -a;
                dp[a]++;
                negative++;
            }
        }
        if(negative <= K){
            if(negative > 0){
                K %= negative;
            }
            if((K % 2) == 1){
                return sum - min * 2;
            }else{
                return sum;
            }
        }else{
            int index = 100;
            while(K > 0){
                while(dp[index] ==  0){
                    index--;
                }
                int div = Math.min(K,dp[index]);
                sum += index * div;
                K -= div;
                dp[index] -= div;
                index--;
            }
            return sum;
        }
    }

    public static void main(String[] args) {
        int[] A = {3,3,-2,2};
        lc1005 s = new lc1005();
        int res = s.largestSumAfterKNegations(A,2);
        System.out.println(res);
    }
}